#矩阵A0,A1,...,An-1
#大小[p0,p1],[p1,p2],...,[pn-1,pn]
def matrix_chain_order(p):
    n=len(p)-1
    m=[[None]*n for i in xrange(n)]
    s=[[None]*n for i in xrange(n)]
    for i in xrange(n):
        m[i][i]=0
        s[i][i]=i
    for l in xrange(2,n+1): #length from 2 to n
        for i in xrange(n-l+1):
            j=i+l-1
            for k in xrange(i,j): #(i,k)(k+1,j)
                q=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]
                if m[i][j] is None or q<m[i][j]:
                    m[i][j]=q
                    s[i][j]=k
    return m,s
def print_optimal_parens(s,i,j):
    if i==j:
        print i,
    else:
        print '(',
        print_optimal_parens(s,i,s[i][j])
        print_optimal_parens(s,s[i][j]+1,j)
        print ')',
def do_print_optimal_parens(s):
    print_optimal_parens(s,0,len(s)-1)
    print
def print_ms(x):
    n=len(x)
    width=len(str(x[0][-1]))
    print
    for l in xrange(n,0,-1):
        for i in xrange(n-l+1):
            j=i+l-1
            print '{0:{w}}'.format(x[i][j],w=width),
        print

if __name__=='__main__':
    p=[30,35,15,5,10,20,25]
    m,s=matrix_chain_order(p)
    print 'optimal parens:',
    do_print_optimal_parens(s)
    print 'm:',
    print_ms(m)
    print 's:',
    print_ms(s)
